https://leetcode.cn/problems/valid-triangle-number/description/
给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。


O(N)=N*LOGN+N^2

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        int maxi=nums.size()-1;
        int ans=0;
        while(maxi>=2)
        {
            int max=nums[maxi];
            int left=0,right=maxi-1;
            while(left<right)
            {
                if(nums[left]+nums[right]>max) //最小加最大满足
                {   
                    ans+=right-left;
                    --right;
                }
                else
                {
                    ++left;
                }
            }
            --maxi;
        }
        return ans;
    }
};



class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        int maxi=nums.size()-1;
        int ans=0;
        while(maxi>=2)
        {
            int max=nums[maxi];
            int left=0,right=maxi-1;
            while(left<right)
            {
                while(left<right)
                {
                    if(nums[left]+nums[right]>max) //最小加最大满足
                    {   
                        ans+=right-left;
                        --right;
                        break;
                    }
                     else
                    {
                        ++left;
                    }
                }
            }
            --maxi;
        }
        return ans;
    }
};